1. Field of the Invention
The present invention relates to texture compression techniques.
2. Background of Invention
Compression and decompression intended to minimize the memory size needed to store 2D textures is a promising field of application for these techniques in the 3D graphic domain. This possible field of use is becoming more and more significant as the dimensions and number of these textures tend to increase in real applications. The level of detail tends to increase as required by some applications, such as 3D games, and, without the help of such techniques, memory size and bandwidth for access would tend to require increasing performance levels hardly sustainable in mobile, ultra low power, handheld systems. More to the point, these techniques are becoming increasingly important in wireless phone architectures with 3D games processing capabilities.
For example, assuming a texture dimension of 512×512 pixels 16 bit/color each and a depth of 3, the amount of memory needed is 1.5 M bytes. Assuming 20-30 frames per second, the memory bandwidth is 30 to 45 Mbytes/s.
Additional background information on this topic can be gathered from “Real-Time Rendering” by Tomas Akenine-Möller and Eric Haines, A. K. Peters Ltd, 2nd edition, ISBN 1568811829.
A well-known solution in this scenario was developed by the company S3; the related algorithm is designated S3TC (where TC stands for Texture Compression).
This has become a widely used de-facto standard and is included in the Microsoft DirectX libraries with adhoc API support.
Compression is performed off-line at compile time and the textures are stored in the main memory. Decompression processes act to compress textures accessing the memory run-time. This means that only decompression is implemented in hardware form while compression is not.
Important parameters for the decompression engine are: steps needed to decompress textures and possible parallel operation; low latency between data-access-from-memory and data-out-from the decompression engine.
In order to better understand operation of the S3TC algorithm one may refer to an image in RGB format, where each color component R (Red) or G (Green) or B (Blue) is a sub-image composed by N pixels in the horizontal dimension and M pixels in vertical dimension. If each color component is coded with P bits, the number of bits per image is N*M*3*P.
For example, assuming N=M=256 and P=8, then the resulting size is 1,572,864 bits. If each sub-image R or G or B is decomposed in not-overlapped blocks of Q pixels in the horizontal dimension and S pixel in the vertical dimension, the number of blocks per sub-image is (N*M)/(Q*S) while per image is [3(NM/(Q*S(WM)] and the number of bits per block is [3*(Q*S)]*P. If, for example Q=S=4 and P=8, then the resulting size of each block is 384 bits. If the number of bits per channel is R=5, G=6, B=5 then the resulting size of each block per image is (4*4)*(5+6+5)=256 bits. The S3TC algorithm is able to compress such an amount of data by 6 times when R=8, G=8, B=8 and 4 times when R=5, G=6, B=5. 64 bits compose the resulting compressed block always sent to decompression stage. This number is the results of the coding steps described below assuming Q=S=4.
To sum up, operation of the S3TC algorithm may be regarded as comprised of the following steps:
i) Decompose the R G B image in non overlapped Q=4*S=4 blocks of R G B colors
ii) Consider the following block composed by 16 pixels each one composed by R, G and B color components:
Pij=Rij U Gij U Bij (this denotes the pixel at the ij position the R G B image, and U is the union operator)
(R11 G11 B11)(R12 G12 B12)(R13 G13 B13)(R14 G14 B14)(R21 G21 B21)(R22 G22 B22)(R23 G23 B23)(R24 G24 B24)(R31 G31 B31)(R32 G32 B32)(R33 G33 B33)(R34 G34 B34)(R41 G41 B41)(R42 G42 B42)(R43 G43 B43)(R44 G44 B44)
iii) Decompose the block above in three sub-blocks called sub-block R, sub-block G and sub-block B as shown hereinbelow, each block including only one color component:
R11 R12 R13 R14sub-block RR21 R22 R23 R24R31 R32 R33 R34R41 R42 R43 R44G11 G12 G13 G14sub-block GG21 G22 G23 G24G31 G32 G33 G34G41 G42 G43 G44B11 B12 B13 B14sub-block BB21 B22 B23 B24B31 B32 B33 B34B41 B42 B43 B44as shown in FIG. 1.
Specifically, FIG. 1 shows RGB blocks ordered in different planes, with a RGB block shown on the left and a corresponding de-composition shown on the right.
iv) Sort in ascending order each sub-block color
v) Detect the black color, which is a pixel made of R=0 and G=0 and B=0
vi) If the black color is not detected, then set a color palette made by                a. 1st color is the minimum value of sub-block R, minimum value of sub-block G, minimum value of sub-block B.        b. 2nd color is the maximum value of sub-block R, maximum value of sub-block G, maximum value of sub-block B        c. 3rd is composed by (2*min R+max R)/3, (2*min G+max G)/3, (2*min B+max B)/3        d. 4th is composed by (min R+2*max R)/3, (min G+2*max G)/3, (min B+2*max B)/3        
vii) Otherwise, if black color is detected then set a color palette made by                a. 1st color is minimum value of sub-block R, sub-block G, sub-block B where each of them must not be equal to zero (the black color component) at the same time        b. 2nd color is maximum value of sub-block R, sub-block G, sub-block B        c. 3rd is composed by (min R+max R)/2, (min G+max G)/2, (min B+max B)/2        d. 4th is the black color that has R,G,B components equal to zero        
viii) If black color is not detected, define the look-up color palette as
                              Look          ⁢                      -                    ⁢          up          ⁢                                          ⁢          table                =                ⁢                  [                                                                                          Min                    ⁢                                                                                  ⁢                    R                                    ,                                                                                                                                      ⁢                                                            Int                      ⁢                      1                      ⁢                      R                                        ,                                                                                                                    Int                    ⁢                    2                    ⁢                    R                                    ,                                                                                                                                      ⁢                                      Max                    ⁢                                                                                  ⁢                    R                                                                                ]                                                ⁢                  [                                                                                          Min                    ⁢                                                                                  ⁢                    G                                    ,                                                                                                  Int                    ⁢                    1                    ⁢                    G                                    ,                                                                                                  Int                    ⁢                    2                    ⁢                    G                                    ,                                                                                                                                      ⁢                                      Max                    ⁢                                                                                  ⁢                    G                                                                                ]                                                ⁢                  [                                                                                          Min                    ⁢                                                                                  ⁢                    B                                    ,                                                                                                  Int                    ⁢                    1                    ⁢                    B                                    ,                                                                                                  Int                    ⁢                    2                    ⁢                    B                                    ,                                                                                                                                      ⁢                                      Max                    ⁢                                                                                  ⁢                    B                                                                                ]                    
If black color is detected define the color palette as
                              Look          ⁢                      -                    ⁢          up          ⁢                                          ⁢          table                =                ⁢                  [                                                                                          Min                    ⁢                                                                                  ⁢                    R                                    ,                                                                                                                                      ⁢                                                            Int                      ⁢                      1                      ⁢                      R                                        ,                                                                                                                                                        ⁢                                      Max                    ⁢                                                                                  ⁢                    R                                                                              0                                              ]                                                ⁢                  [                                                                                          Min                    ⁢                                                                                  ⁢                    G                                    ,                                                                                                  Int                    ⁢                    1                    ⁢                    G                                    ,                                                                                                                                      ⁢                                      Max                    ⁢                                                                                  ⁢                    G                                                                              0                                              ]                                                ⁢                  [                                                                                          Min                    ⁢                                                                                  ⁢                    B                                    ,                                                                                                  Int                    ⁢                    1                    ⁢                    B                                    ,                                                                                                                                      ⁢                                      Max                    ⁢                                                                                  ⁢                    B                                    ⁢                                                                                                                    0                                              ]                    
ix) Associate the following 2 bits code (in boldface, under the palette) to each column of the above palette
                                          Look            ⁢                          -                        ⁢            up            ⁢                                                  ⁢            table                    =                    ⁢                      [                                                                                                      Min                      ⁢                                                                                          ⁢                      R                                        ,                                                                                                                                                      ⁢                                                                  Int                        ⁢                        1                        ⁢                        R                                            ,                                                                                                                                  Int                      ⁢                      2                      ⁢                      R                                        ,                                                                                                                                                      ⁢                                          Max                      ⁢                                                                                          ⁢                      R                                                                                            ]                                                                  ⁢                      [                                                                                                      Min                      ⁢                                                                                          ⁢                      G                                        ,                                                                                                              Int                      ⁢                      1                      ⁢                      G                                        ,                                                                                                              Int                      ⁢                      2                      ⁢                      G                                        ,                                                                                                                                                      ⁢                                          Max                      ⁢                                                                                          ⁢                      G                                                                                            ]                                                                  ⁢                      [                                                                                                      Min                      ⁢                                                                                          ⁢                      B                                        ,                                                                                                              Int                      ⁢                      1                      ⁢                      B                                        ,                                                                                                              Int                      ⁢                      2                      ⁢                      B                                        ,                                                                                                                                                      ⁢                                          Max                      ⁢                                                                                          ⁢                      B                                                                                            ]                                                                        ⁢                      00            ⁢                                                  ⁢            01            ⁢                                                  ⁢            10            ⁢                                                  ⁢            11                                                                        Look            ⁢                          -                        ⁢            up            ⁢                                                  ⁢            table                    =                    ⁢                      [                                                                                                      Min                      ⁢                                                                                          ⁢                      R                                        ,                                                                                                                                                      ⁢                                                                  Int                        ⁢                        1                        ⁢                        R                                            ,                                                                                                                                                                          ⁢                                          Max                      ⁢                                                                                          ⁢                      R                                                                                        0                                                      ]                                                                  ⁢                      [                                                                                                      Min                      ⁢                                                                                          ⁢                      G                                        ,                                                                                                              Int                      ⁢                      1                      ⁢                      G                                        ,                                                                                                                                                      ⁢                                          Max                      ⁢                                                                                          ⁢                      G                                                                                        0                                                      ]                                                                  ⁢                      [                                                                                                      Min                      ⁢                                                                                          ⁢                      B                                        ,                                                                                                              Int                      ⁢                      1                      ⁢                      B                                        ,                                                                                                                                                      ⁢                                          Max                      ⁢                                                                                          ⁢                      B                                        ⁢                                                                                                                                  0                                                      ]                                                                           ⁢                      00            ⁢                                                  ⁢            01            ⁢                                                  ⁢            10            ⁢                                                  ⁢            11                              
x) For each Pij=Rij U Gij U Bij (where i ranges from 1 to Q=4 and j ranges from 1 to S=4) compute the Euclidean distance Dist between it and each look-up color as defined above in vi.a,b,c,d or vii.a,b,c,d depending if black color has been detected or not. Note that the difference is within a homologue color component (between R or G or B).Dist1=√(|Rij−MinR|2+|Gij−MinG|2+|Bij−MinB|2)Dist2=√(|Rij−Int1R|2+|Gij−Int1G|2+|Bij−Int1B|2)Dist3=√(|Rij−Int2R|2+|Gij−Int2G|2+|Bij−Int2B|2)Dist4=√(|Rij−MaxR|2+|Gij−MaxG|2+|Bij−MaxB|2)
xi) For each Pij=Rij U Gij U Bij find the minimum distance among Dist1, Dist2, Dist3 and Dist4. For example let this be Dist1.
xii) Send to a decoder process the code associated to the color enclosed in the look-up table that has the minimum distance. If it is Dist1 then the code is 00.
xiii) The decoder receives for each Q*S block as shown in FIG. 2                a. 2 bits code for each Pij that are addresses to the look-up table        b. MinR MinG MinB        c. MaxR MaxG MaxB        
xiv) If Min is received before Max by the decoder, then black has been detected by the encoder otherwise not
xv) As shown in FIG. 2, the decoder operates as described in steps vi or vii depending on black color detection                a. Int1R Int1G Int1B        b. Int2R Int2G Int2B        
xvi) As shown in FIG. 2, the decoder addresses a look-up table with 2 bits code associated to each Pij and replaces it with the color stored in the look-up table color palette. Specifically ST, LUT, and CT indicate the source text, the look-up table, and the compressed text, respectively.
FIG. 3 shows how the data sent to the decoder are arranged in a bitstream and if the black color is not detected, while FIG. 4 shows the opposite case.
As stated before, the compression ratio is 6:1 or 4:1. This is because if colors are in R=8 G=8 B=8 format then 384 bits are coded with 64 (384/64=6) and if colors are in R=5 G=6 B=5 format then 256 bits are coded with 64 (256/64=4).
As shown in FIGS. 3 and 4, the sum of all the bits amounts to 64.